package lc_剑指_Offer_II_087_复原_IP;

import java.util.ArrayList;
import java.util.List;

public class Solution {

//	输入：s = "25525511135"
//	输出：["255.255.11.135","255.255.111.35"]

	List<String> ans;
	int n;
	char[] cs;
	List<String> list;

	public List<String> restoreIpAddresses(String s) {
		cs = s.toCharArray();
		n = s.length();
		ans = new ArrayList<>();
		list = new ArrayList<>();
		f(0);
		return ans;
	}

	private void f(int i) {
		if (i == n && list.size() == 4) {
			ans.add(String.join(".", list));
			return;
		}
		if (i == n || list.size() == 4) {
			return;
		}
		int t = cs[i] == '0' ? i + 2 : n + 1;
		for (int j = i + 1; j < t; j++) {
			String cur = new String(cs, i, j - i);
			if (Integer.valueOf(cur) > 255) {
				return;
			}
			if (Integer.valueOf(cur) < 256) {
				list.add(cur);
				f(j);
				list.remove(list.size() - 1);
			}
		}
	}

}